package com.mzy.linear_struct.hot100.动态规划;

import java.util.Arrays;

/**
 * @Author: mizy3
 * @Date: 2024/08/11/下午7:17
 * @Description:
 */
public class Pro746使用最小花费爬楼梯 {
    private int minCostClimbingStairs(int[] cost) {
        // i表示当前在第n阶台阶上，dp[i]表示n阶台阶前的最小花费
        int[] dp = new int[cost.length + 1];

        dp[0] = 0;
        dp[1] = 0;

        // dp[i] = Math.min(dp[i - 2], dp[i - 1]);
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
            System.out.println(i + " " + dp[i]);
        }
        return dp[dp.length - 1];
    }

    /*public int minCostClimbingStairs(int[] cost) {
        // 确认dp数组，i表示第i阶台阶，dp[i]表示i阶台阶之前的最小花费
        int[] dp = new int[cost.length + 1];
        // 确认递推公式 -> Math.min(dp[i - 1] + cost[i - 1] , dp[i - 2] + cost[i - 2])
        // 初始化 dp 状态
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i < dp.length; i++) {
            int one = dp[i - 1] + cost[i - 1];
            int two = dp[i - 2] + cost[i - 2];
            dp[i] = Math.min(one, two);
        }
        return dp[dp.length - 1];
    }
*/


    public static void main(String[] args) {
        System.out.println(new Pro746使用最小花费爬楼梯().minCostClimbingStairs(new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1}));
    }


}
